#include<string>
#include<vector>
#include<array>
#include<unordered_map>
class Solution {
public:
    int findDuplicate(std::vector<int>& nums) {
        int fast = 0;
        int slow = 0;
        do
        {
            fast = nums[fast];
            fast  = nums[fast];
            slow = nums[slow];
        }while (fast!=slow);
        fast=0;
        do
        {
            slow = nums[slow];
            fast = nums[fast];
        }while (slow!=fast);
        return fast;
    }
};